1. Field of the Invention
The present invention relates to a method, a computer program product and a data structure for a representation of graphical information of a two- or three-dimensional object.
2. Description of Related Art
In recent years, it plays a key role in various fields including design and production using computer-assisted design (CAD) system and/or computer-assisted manufacturing (CAM) system, environmental recognition techniques of robots, various scientific simulations, computer graphics, and the like to perform graphics data processing on a computer display image for two- or three-dimensional object modeling and to store the data representing the graphics information structured in a specific form on a storage medium capable of being accessed and read by a computer. In particular, there have been proposed, in the technical field of CAD/CAM system, a variety of data structures for storing and saving edited graphics on a storage medium.
Data structures composed of data items of point and edges are widely used to represent graphs for modeling of polygonal or two-dimensional objects or polyhedral or three-dimensional objects in early CAD systems. However, as the capacity of computer memory was increased dramatically resulting from rapid development of computer technology, a recent tendency is toward employing an application-oriented representational form of data structures capable of allowing data to be relatively redundant so as to allow provision of voluminous information and easy and short-time data processing. A basic data structure that is nowadays most-widely used in CAD systems is what is called a half-edge data structure that is an advanced, predigested data structure of the winged-edge data structure propounded by B. G. Baumgart. The half-edge data structure is capable of flexibly data processing for modeling of polyhedral or solid models.
Reference is made to FIG. 39 showing conceptual illustration for ease of explanation of the prior art half-edge data structure for a representation of polyhedral solid modeling for the purpose of providing an outline architecture of half-edge structure that will enhance an understanding of a point-based data structure of the present invention. A polyhedral solid generally has two adjacent faces, namely a face pf that is closed edges pccw, e, pcw and other edges, and a face nf that is closed by edges ncw, e, nccw and other edges, as shown (a) in FIG. 39. A vertex nw is an intersection between the edges ppcw, e and ncw. A vertex pv is an intersection between the edges pcw, e and nccw. The adjacency of the edges around the vertex forms a circular-ordered list. In other words, the half-edge structure represents adjacency information of the edge e by splitting it into two edge structures e and e′, each related to one of the two edge ends which is adjacent to other edge ends around a vertex. More specifically, the half-edge data structure gives the edge e an upward direction and the edge e′ a downward direction and represents adjacency relationships of the edges pcw, e and pccw of the face pf and adjacency relationships of the edges ncw, e′ and pccw′ of the face pf′ as viewed from outside the solid volume looking toward the surface.
Although the half-edge data structure has a high degree of redundancy, it has been universally applied for interactive solid modeling through CAD because of the possibility of efficient data processing and short-time requirement for creation of an executable program.
However, it is very troublesome to represent a graph of a three-dimensional solid object having planar and curved surfaces even by the half-edge data structure. This is because planer and curved surfaces are represented in different data formats and, in consequence, it is hard pressed to bring data for interface between these planar and curved surfaces consistency with each other. In addition, it is considerably time and energy-consuming to create a program, besides the program itself and data spend a huge storage space.
There have been proposed CAM systems that are designed to represent a graph as close as having an imaginarily precise interface between planer and curved surfaces only for vision and display purpose. In such a system, the representation is not a physical solid model, an adverse consequence is encountered in the case of determining a tool path or rout for numerically controlled machine tools.
The data manipulation of a representation of a curved surface is an extremely intractable job. When defining a quadratic surface by an algebraic function, it is essential to provide data for a representation of a domain of function to which constants or variables of the algebraic function are valid. In particular, when defining a quadratic surface by a spline curve, a B-spline curve, or a Non-Uniformed Rotational B-Spline (NURBS) curve, data should contain coordinate information on control points of the curve or passing points of the curve. Further, when analyzing a curved surface by splitting it into diagonal segments that are impossible to lie in a matrix pattern, it is necessary to have an extraordinary data structure available.
Further, it has become routine with holding alteration history information in conventional interactive graph representations that, when executing a command to cancel a job or to retrieve the cancelled job, it is essential to start the job over again according to a given command history that is hold separately from the graphic data or to execute a counter command to produce the same effect as a cancel of the job if the immediately preceding command is reversible. There have been proposed data structures capable of holding alteration history information therein. Such a data structure encounters a decline in data processing efficiency and, in consequence, less utilized in CAD systems.
In order to manipulate an embedded geometric graph of a two- or three-dimensional object represented data structures with a computer, one has no other choice than coping with required processes with different types of data structures according to complex configuration of an object. This forces the computer to store huge volumes of data and results in less data processing efficiency.
There have been proposed surface-based data structures along with the edge-based data structures as described above. However, even these surface-based data structures are so far not always suitable for a representation of a curved surface. Almost of the existing data structure are incapable of manipulating planar and curved surfaces and/or an interface between two or more curved surfaces in a unified form in the case of a graph representations of a polyhedral solid object with a number of curved surfaces intricately arranged or of a polyhedral solid object with mixed planar and curved surfaces. Therefore, there are still many problems of intractable curved surface to be broken through. Furthermore, as concerns alteration history of a graph, the conventional data structures requires a flood of geometric data, a quantitative increase of data is notable with respect to each alteration and, in consequence, encounters a problem of inefficient data processing.